/*************************************
 *  auth : sunqiang
 *  date : 20170117
 *  desp : red_black_tree opt
 *  		refer to nginx
 *************************************/

#include <stdio.h>
#include "sn_rbtree.h"

static inline sn_rbtree_node_t *sn_rbtree_min(sn_rbtree_node_t *node, 
		sn_rbtree_node_t *sentinel);
static inline void sn_rbtree_left_rotate(sn_rbtree_node_t **root,
		sn_rbtree_node_t *sentinel, sn_rbtree_node_t *node);
static inline void sn_rbtree_right_rotate(sn_rbtree_node_t **root, 
		sn_rbtree_node_t *sentinel, sn_rbtree_node_t *node);

void sn_rbtree_insert(sn_rbtree_t *tree, sn_rbtree_node_t *node) {
	sn_rbtree_node_t    **root;
	sn_rbtree_node_t    *temp;	
	sn_rbtree_node_t    *sentinel;

	root = (sn_rbtree_node_t **) &tree->root;
	sentinel = tree->sentinel;

	if (*root == sentinel) {
		node->parent = NULL;
		node->left = sentinel;
		node->right = sentinel;
		sn_rbt_black(node);
		*root = node;

		return;
	}

	tree->insert(*root, node, sentinel);

	while (node != *root && sn_rbt_is_red(node->parent)) {

		if (node->parent == node->parent->parent->left) {
			temp = node->parent->parent->right;

			if (sn_rbt_is_red(temp)) {
				sn_rbt_black(node->parent);
				sn_rbt_black(temp);
				sn_rbt_red(node->parent->parent);
				node = node->parent->parent;

			} else {
				if (node == node->parent->right) {
					node = node->parent;
					sn_rbtree_left_rotate(root, sentinel, node);
				}

				sn_rbt_black(node->parent);
				sn_rbt_red(node->parent->parent);
				sn_rbtree_right_rotate(root, sentinel, node->parent->parent);
			}

		} else {
			temp = node->parent->parent->left;

			if (sn_rbt_is_red(temp)) {
				sn_rbt_black(node->parent);
				sn_rbt_black(temp);
				sn_rbt_red(node->parent->parent);
				node = node->parent->parent;

			} else {
				if (node == node->parent->left) {
					node = node->parent;
					sn_rbtree_right_rotate(root, sentinel, node);
				}

				sn_rbt_black(node->parent);
				sn_rbt_red(node->parent->parent);
				sn_rbtree_left_rotate(root, sentinel, node->parent->parent);
			}
		}
	}

	sn_rbt_black(*root);
}

void sn_rbtree_delete(sn_rbtree_t *tree, sn_rbtree_node_t *node) {
	int16_t           red;
	sn_rbtree_node_t  **root;
	sn_rbtree_node_t  *sentinel;
	sn_rbtree_node_t  *subst;
	sn_rbtree_node_t  *temp;
	sn_rbtree_node_t  *w;

	root = (sn_rbtree_node_t **) &tree->root;
	sentinel = tree->sentinel;

	if (node->left == sentinel) {
		temp = node->right;
		subst = node;

	} else if (node->right == sentinel) {
		temp = node->left;
		subst = node;

	} else {
		subst = sn_rbtree_min(node->right, sentinel);

		if (subst->left != sentinel) {
			temp = subst->left;
		} else {
			temp = subst->right;
		}
	}

	if (subst == *root) {
		*root = temp;
		sn_rbt_black(temp);

		/* DEBUG stuff */
		node->left = NULL;
		node->right = NULL;
		node->parent = NULL;
		node->key = 0;

		return;
	}

	red = sn_rbt_is_red(subst);

	if (subst == subst->parent->left) {
		subst->parent->left = temp;

	} else {
		subst->parent->right = temp;
	}

	if (subst == node) {

		temp->parent = subst->parent;

	} else {

		if (subst->parent == node) {
			temp->parent = subst;

		} else {
			temp->parent = subst->parent;
		}

		subst->left = node->left;
		subst->right = node->right;
		subst->parent = node->parent;
		sn_rbt_copy_color(subst, node);

		if (node == *root) {
			*root = subst;

		} else {
			if (node == node->parent->left) {
				node->parent->left = subst;
			} else {
				node->parent->right = subst;
			}
		}

		if (subst->left != sentinel) {
			subst->left->parent = subst;
		}

		if (subst->right != sentinel) {
			subst->right->parent = subst;
		}
	}

	node->left = NULL;
	node->right = NULL;
	node->parent = NULL;
	node->key = 0;

	if (red) {
		    return;
	}

	while (temp != *root && sn_rbt_is_black(temp)) {
		if (temp == temp->parent->left) {
			w = temp->parent->right;

			if (sn_rbt_is_red(w)) {
				sn_rbt_black(w);
				sn_rbt_red(temp->parent);
				sn_rbtree_left_rotate(root, sentinel, temp->parent);
				w = temp->parent->right;
			}

			if (sn_rbt_is_black(w->left) && sn_rbt_is_black(w->right)) {
				sn_rbt_red(w);
				temp = temp->parent;

			} else {
				if (sn_rbt_is_black(w->right)) {
					sn_rbt_black(w->left);
					sn_rbt_red(w);
					sn_rbtree_right_rotate(root, sentinel, w);
					w = temp->parent->right;
				}

				sn_rbt_copy_color(w, temp->parent);
				sn_rbt_black(temp->parent);
				sn_rbt_black(w->right);
				sn_rbtree_left_rotate(root, sentinel, temp->parent);
				temp = *root;
			}
		} else {
			w = temp->parent->left;

			if (sn_rbt_is_red(w)) {
				sn_rbt_black(w);
				sn_rbt_red(temp->parent);
				sn_rbtree_right_rotate(root, sentinel, temp->parent);
				w = temp->parent->left;
			}

			if (sn_rbt_is_black(w->left) && sn_rbt_is_black(w->right)) {
				sn_rbt_red(w);
				temp = temp->parent;

			} else {
				if (sn_rbt_is_black(w->left)) {
					sn_rbt_black(w->right);
					sn_rbt_red(w);
					sn_rbtree_left_rotate(root, sentinel, w);
					w = temp->parent->left;
				}

				sn_rbt_copy_color(w, temp->parent);
				sn_rbt_black(temp->parent);
				sn_rbt_black(w->left);
				sn_rbtree_right_rotate(root, sentinel, temp->parent);
				temp = *root;
			}
		}
	}
	sn_rbt_black(temp);
}

void *
sn_rbtree_lookup(sn_rbtree_node_t * root, sn_rbtree_node_t *sentinel, unsigned long key)
{
	sn_rbtree_node_t              *node;

	node = root;    

	while (node != sentinel) {

		if (key < node->key) {
			node = node->left;
			continue; 
		} 

		if (key > node->key) {
			node = node->right;
			continue; 
		} 

		/* key == node->key */
		return node;
	}

	/* not found */
	return NULL;
}

void
sn_rbtree_init_insert_value(sn_rbtree_node_t *temp, sn_rbtree_node_t *node, sn_rbtree_node_t *sentinel)
{
	sn_rbtree_node_t            **p = NULL;

	for ( ;; ) {

		if (node->key < temp->key) {

			p = &temp->left;
		} else if (node->key > temp->key) {

			p = &temp->right;
		} else {

			assert(0 == 0);
		}

		if (*p == sentinel) {
			break;
		}

		temp = *p;
	}

	*p = node;
	node->parent = temp;
	node->left = sentinel;
	node->right = sentinel;
	sn_rbt_red(node);    
}

static inline sn_rbtree_node_t *
sn_rbtree_min(sn_rbtree_node_t *node, sn_rbtree_node_t *sentinel)
{
	while (node->left != sentinel) {
		node = node->left;
	}

	return node;
}

void sn_rbtree_insert_value(sn_rbtree_node_t *temp, sn_rbtree_node_t *node,
		    sn_rbtree_node_t *sentinel) {

	sn_rbtree_node_t  **p;

	for ( ;; ) {

		p = (node->key < temp->key) ? &temp->left : &temp->right;

		if (*p == sentinel) {
			break;
		}

		temp = *p;
	}

	*p = node;
	node->parent = temp;
	node->left = sentinel;
	node->right = sentinel;
	sn_rbt_red(node);
}

static inline void sn_rbtree_left_rotate(sn_rbtree_node_t **root,
		sn_rbtree_node_t *sentinel, sn_rbtree_node_t *node) {

	sn_rbtree_node_t  *temp;

	temp = node->right;
	node->right = temp->left;

	if (temp->left != sentinel) {
		    temp->left->parent = node;
	}

	temp->parent = node->parent;

	if (node == *root) {
		    *root = temp;

	} else if (node == node->parent->left) {
		    node->parent->left = temp;

	} else {
		    node->parent->right = temp;
	}

	temp->left = node;
	node->parent = temp;
}

static inline void sn_rbtree_right_rotate(sn_rbtree_node_t **root, 
		sn_rbtree_node_t *sentinel, sn_rbtree_node_t *node) {

	sn_rbtree_node_t  *temp;

	temp = node->left;
	node->left = temp->right;

	if (temp->right != sentinel) {
		    temp->right->parent = node;
	}

	temp->parent = node->parent;

	if (node == *root) {
		    *root = temp;

	} else if (node == node->parent->right) {
		    node->parent->right = temp;

	} else {
		    node->parent->left = temp;
	}

	temp->right = node;
	node->parent = temp;
}
